Yeltsin từng là một thành viên Đảng cộng sản Liên Xô (CPSU) từ 1961 đến tháng 7 năm 1990, và đã bắt đầu làm việc trong bộ máy hành chính của đảng năm 1968. Sau này ông đã bình luận về các quan điểm cộng sản của mình:

"Tôi đã chân thành tin tưởng vào các lý tưởng về sự công bằng do đảng tuyên truyền, và cũng có cảm giác ấy khi gia nhập đảng, nghiên cứu toàn bộ các hiến chương, các chương trình và các giáo điều, đọc lại các tác phẩm của Lênin, Marx và Engels."

Năm 1977 với tư cách là lãnh đạo đảng tại Sverdlovsk, ông ra lệnh phá huỷ Ipatiev House nơi vị Sa hoàng cuối cùng bị ám sát. Ipatiev House bị phá hủy trong một đêm, rạng sáng ngày 18 tháng 9 năm 1977. Cũng trong thời gian Yeltsin nắm quyền ở Sverdlovsk, một tòa nhà lớn của Đảng cộng sản được xây dựng và được những người sống ở đó gọi là "Răng trắng". Trong 30 năm hoạt động với tư cách một đảng viên cộng sản, Yeltsin đã phát triển các mối quan hệ với những nhân vật chủ chốt bên trong cơ cấu quyền lực Xô viết.

Ông được chỉ định vào Bộ chính trị, và kiêm chức "Thị trưởng" Moskova (bí thư thứ nhất Đảng Cộng sản Liên Xô Ủy ban thành phố Mátxcơva) từ 24 tháng 12 năm 1985 đến 1987. Ông được đề bạt lên tới các chức vụ đó nhờ Mikhail Gorbachev và Yegor Ligachev, những người tin tưởng rằng Yeltsin sẽ trở thành "người đằng mình". Yeltsin cũng được cấp một căn nhà ở thôn quê (dacha) trước kia từng là của Gorbachev. Trong thời gian này, Yeltsin tự thể hiện mình như một nhà cải cách và quần chúng (ví dụ, ông dùng xe điện bánh hơi đi làm), sa thải và cải tổ bộ máy nhân sự của mình nhiều lần. Những sáng kiến của ông gây được tiếng vang trong dân chúng Mátxcơva.

Năm 1987, sau một cuộc đối đầu với Yegor Ligachev, người theo đường lối cứng rắn, và cuối cùng là cả với Mikhail Gorbachev về vụ vợ Gorbachev, Raisa, dính vào các công việc nhà nước, Yeltsin bị hất khỏi các cương vị cao trong đảng. Ngày 21 tháng 10 năm 1987 trong phiên họp toàn thể Ủy ban trung ương Đảng Cộng sản Liên Xô, Yeltsin, không được Gorbachev đồng ý trước, to tiếng lên án Bộ chính trị. Ông bày tỏ sự bất bình với cả những bước tiến hành cải tổ chậm chạp trong xã hội và sự lệ thuộc của Tổng bí thư, sau đó đòi từ chức khỏi Bộ chính trị và nói thêm rằng Ủy ban thành phố sẽ quyết định việc ông có rời khỏi chức vụ bí thư thứ nhất Ủy ban đảng thành phố Mátxcơva. Trong phần trả lời của mình, Gorbachev đã buộc tội Yeltsin "non nớt về chính trị" và "hoàn toàn vô trách nhiệm", và đặt vấn đề bãi miễn chức vụ bí thư thứ nhất của Yeltsin tại phiên họp toàn thể Ủy ban đảng thành phố Mátxcơva. Không ai ủng hộ Yeltsin. Những lời chỉ trích Yeltsin tiếp tục diễn ra ngày 11 tháng 11 năm 1987 tại phiên họp của Ủy ban đảng thành phố Mátxcơva. Ông nhận rằng bài phát biểu của ông là một sai lầm. Yeltsin bị cách chức bí thư thứ nhất Ủy ban thành phố Mátxcơva. Ông không bị phát vãng hay bị bỏ tù như những trường hợp trước đó, nhưng bị giáng làm phó ủy viên thường trực Ủy ban nhà nước về Xây dựng. Sau khi bị cách chức, Yeltsin phải vào bệnh viện và theo như tin tức đưa ra (sau này đã được Nikolai Ryzhkov xác nhận) đã định tự sát. Ông ở tình trạng rối loạn và nhục nhã nhưng đã bắt đầu sắp đặt kế hoạch trả thù. Cơ hội của ông đến khi Gorbachev thành lập Đại hội đại biểu nhân dân. Ông phục hồi chức vụ và bắt đầu chỉ trích mạnh mẽ Gorbachev, lấy sự chậm chạp trong quá trình cải tổ ở Liên Xô làm mục tiêu.

Những lời chỉ trích của Yeltsin nhắm vào Bộ chính trị và Gorbachev khiến ông phải chịu một chiến dịch bôi nhọ chống lại mình. Những người tổ chức chiến dịch bôi nhọ đó chắc chắn đã tin rằng việc tống khứ Yeltsin quá dễ dàng để thực hiện với những vụ scandal gây bởi cách cư xử vụng về của ông. Một bài báo trong tờ Pravda đã miêu tả ông say rượu tại một buổi thuyết trình trong chuyến thăm Hoa Kỳ, và một chương trình TV bình luận về bài diễn văn của ông dường như đã xác nhận thông tin này. Tuy nhiên, tình cảm bất mãn của dân chúng với chế độ đang rất mạnh mẽ, và bất kỳ một nỗ lực nào nhằm bôi nhọ Yeltsin chỉ càng khiến ông nổi tiếng hơn. Một tai nạn khác xảy ra với Yeltsin khi ông bị ngã từ một cây cầu. Bình luận về vụ này, Yeltsin bóng gió ám chỉ rằng ông bị ngã vì những kẻ thù của perestroika. Tuy nhiên, những người đối lập với ông lại cho rằng đó chỉ đơn giản vì ông say rượu.